Non-volatile memory systems, such as flash memory, are used in digital computing systems as a means to store data and have been widely adopted for use in consumer products. Flash memory may be found in different forms, for example in the form of a portable memory card that can be carried between host devices or as a solid state disk (SSD) embedded in a host device. In SSDs or similar storage devices, a fine granularity logical-to-physical address mapping table is often helpful to provide improved performance. This table can typically be very large. The full table, or subparts of it, is generally necessary to perform read and write tasks, so it is desirable to store a working copy of the mapping table in fast access memory such as dynamic random access memory (DRAM) to ease read and write overhead. However, it may not be economically or technologically viable to use a DRAM sufficiently large to hold the entire table for a memory system.
If the entire mapping table is not held in DRAM, then read and write performance may slow down. For example, when data is written to a flash memory of a SSD, the mapping table or other data structure that tracks the location of data in the flash memory must be updated. The time involved in updating data structures for file systems to reflect changes to files and directories, and accessing these data structures, may affect the performance of the storage device.
Two broad types of mapping tables exist: a fixed-size entry mapping table and a variable-length entry mapping table. The former is often easier to implement and allows a direct address lookup. The latter, in the best cases, gives a reduced mapping table size but can lead to a larger mapping table size in worst case data fragmentation situations. A hybrid format maybe possible, however any method containing a variable-length entry implementation generally adds significantly to the complexity due to memory allocation required for contraction and expansion of the mapping table.
The mapping table types above can only ever guarantee a maximum mapping table size directly related to the data mapping granularity. If the DRAM is not big enough to hold this, as is generally the case, then a mechanism is required to swap in and out areas of the mapping table from flash to DRAM and vice versa. A drawback to such a scheme is evident during random workloads when large fractions of the time the mapping table for the requested data will not be stored in DRAM thus extra flash reading to access the needed portions of the table is required. A variable length copy of the mapping table in DRAM can overcome this if the fragmentation is low, but at the cost of greater algorithmic complexity which may be amount to more loss in performance than is gained by reducing the required flash reads.